CF85E Guard Towers

注意题目中的这句话 : 使得同组内的两座塔的曼哈顿距离的最大值最小 , 很容易想到二分。

考虑二分一个长度lenlen,显然,当两个点的曼哈顿距离大于lenlen时,它们不能属于同一个集合。

我们将这样的点对连一条边,原问题等价与判断新图是否为一个二分图

这个很好做到,我们找一个未被遍历的点uu,并向他的子节点扩散。

如果uu的子节点vv未染色,就染成与点uu相反的颜色。

不然,如果点uu的颜色与点vv的颜色相同,说明原图不是二分图。

重复以上操作,直到遍历完每一条边。

然后,我们发现,方案数为2的联通块数量次方。因为每个联通快的x部和y部可以交换,就有两种分法。联通块数量可以在遍历图时顺便求出。

其实此题并不难,远远不到黑题水准。

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define Mod 1000000007

const int MAXN = 5000;
int n , m , u , v , num , Ans;
struct node1{
	int x , y;
}Point[ MAXN + 5 ];

int Fabs( int x ) {
	return x < 0 ? -x : x;
}
int Dis( int p1 , int p2 ) {
	return Fabs( Point[ p1 ].x - Point[ p2 ].x ) + Fabs( Point[ p1 ].y - Point[ p2 ].y );
}
int Quick_pow( int x , int po ) {
	int Ans = 1;
	while( po ) {
		if( po % 2 )
			Ans = 1ll * Ans * x % Mod;
		x = 1ll * x * x % Mod;
		po /= 2;
	}
	return Ans;
}

int Color[ MAXN + 5 ];
bool dfs( int u , int len ) {
	for( int v = 1 ; v <= n ; v ++ ) { 
		if( u == v || Dis( u , v ) <= len ) continue;
		if( Color[ v ] == -1 ) {
			Color[ v ] = !Color[ u ];
			if( !dfs( v , len ) ) return 0;
		}
		else if( Color[ v ] == Color[ u ] )
			return 0;	
	}
	return 1;
}
bool check( int len ) {
	int cnt = 0; 
	memset( Color , -1 , sizeof( Color ) );
	for( int i = 1 ; i <= n ; i ++ )
		if( Color[ i ] == -1 ) {
			cnt ++;
			if( !dfs( i , len ) ) return 0;
		}
	Ans = len , num = cnt;	
	return 1;
}
int solve( ) {
	int l = 0 , r = 10000 , Mid;
	while( l <= r ) {
		Mid = ( l + r ) / 2;
		if( check( Mid ) )
			r = Mid - 1;
		else
			l = Mid + 1;
	}
	return Ans;	
}

int main( ) {
	scanf("%d",&n);
	for( int i = 1 ; i <= n ; i ++ )
		scanf("%d %d", &Point[ i ].x , &Point[ i ].y );
	printf("%d\n", solve( ) );
	printf("%d\n", Quick_pow( 2 , num ) );
	return 0;
}